package _2_leetcode_21_40._29两数相除;

/**
 * User: Mazexal
 * Date: 2021/1/15
 * 给定两个整数，被除数 dividend 和除数 divisor。将两数相除，要求不使用乘法、除法和 mod 运算符。
 * <p>
 * 返回被除数 dividend 除以除数 divisor 得到的商。
 * <p>
 * 整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/divide-two-integers
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Solution {

    public static void main(String[] args) {
        System.out.println(divide(10, 3));

        System.out.println(divide(7, -3));
    }

    /**
     * @author mazexal
     * 思路就是倍增递归
     */
    public static int divide(int dividend, int divisor) { // 被除数 除数
        // 溢出
        if (divisor == -1 && dividend == Integer.MIN_VALUE) {
            return Integer.MAX_VALUE;
        }
        // 负数判断
        int sign = 1;
        if ((dividend > 0 && divisor < 0) || (dividend < 0 && divisor > 0)) {
            sign = -1;
        }
        int a = dividend > 0 ? -dividend : dividend;
        int b = divisor > 0 ? -divisor : divisor;

        if (a > b) {
            return 0;
        }
        int ans = div(a, b);
        return sign == -1 ? -ans : ans;
    }

    static int div(int a, int b) {
        if (a > b) {
            return 0;
        }
        int count = 1;
        int tb = b;
        // 溢出之后不再小于0
        while (tb + tb >= a && tb + tb < 0) {
            tb += tb;
            count += count;
        }
        return count + div(a - tb, b);
    }
}
